其實原本打算再寫兩天背包問題的（昨天草稿標題都下好了），不過今天寫了一下題目好像可以結束了。

如果有點開 Day9 的延伸資料，會發現好像還有幾種沒寫？例如樹形 DP，這類型 leetcode 沒有，估狗一下會挖到 OI 的東西我們當然就跳過吧。

另外剩下的就是分組背包和方案數，我寫完題目的感覺是，這些和多維背包是類似的邏輯。例如 1155. Number of Dice Rolls With Target Sum，這題被歸類在分組背包（每個背包有多個物品可選擇，一定要選且只能選一個），是在 0-1 背包的基礎上，加入多重方案，所以雖然是二維矩陣，但實際寫出來的迴圈有三層。

而 494. Target Sum 被歸在方案數的類型內，這題需要稍微轉一下，直接去遍歷所有 case 當然不可能，但如果把題目改成「挑出一部份的數字，總和剛好為 [sum(array)-target] / 2」，這樣子就可以確定：把挑出來的這些數字減掉，再加上剩下的數字後，其和會是 target。這種稍微和數學相關，需要點巧思的題目，大概被坑過幾次就會有感覺了。

# 494. Target Sum
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        s = sum(nums)
        if s < target:
            return 0
        if (s-target)%2 == 1:
            return 0

        t = (s-target) // 2
        n = len(nums)

        arr = [[0]*(t+1) for _ in range(n+1)]
        arr[-1][0] = 1

        for i in range(n):
            arr[i][0] = 1
            w = nums[i]
            for j in range(t+1):
                arr[i][j] = arr[i-1][j]
                if j >= w:
                    arr[i][j] +=  arr[i-1][j-w]
        
        return arr[-2][-1]

總之，背包問題的最底層的邏輯都是類似的，第一個維度基本上就是和物品相關，把物品一個個納入考量。第二維度就會放重量限制，裡面的內容則是存 value。其實寫過 0-1 背包、完全背包，再多找幾題多維背包的題目來練手，應該就可以摸懂七八成了吧。

最後補充一個作弊技巧：看 input 的 array 長度。當長度是 10^5 左右就不會是二維（n^2 的複雜度太高），如果只有 10^3 那 n^2 則沒有問題，真的沒有靈感時可以看一下增加點方向。

• 多維背包
  • 1155. Number of Dice Rolls With Target Sum
• 背包問題求方案數
  • 0-1 背包：494. Target Sum
  • 完全背包：1449. Form Largest Integer With Digits That Add up to Target
  • 多維背包：879. Profitable Schemes
    • 後兩題還沒寫待補QQ

• Total Count: 15